package c_ch11.prim;

import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import c_ch11.WeightedEdge;
import c_ch11.kruskal.Kruskal_try;
import c_ch11.kruskal.WeightedGraph_try;

public class Prim_try_2020_05_16 {

	private ArrayList<WeightedEdge> res = new ArrayList<>();
	private boolean[] visited;
	public Prim_try_2020_05_16(String wGraphFile) {
		
		WeightedGraph_try wg = new WeightedGraph_try(wGraphFile);
		
		visited = new boolean[wg.getV()];
		for (int i = 0; i < visited.length; i++) {
			visited[i] = false;
		}
		
		PriorityQueue<WeightedEdge> pq = new PriorityQueue<>(); 
		visited[0] = true;
		for (Integer weightedEdge : wg.adj(0)) {
			pq.add(new WeightedEdge(0, weightedEdge, wg.weight(0, weightedEdge)));
		}
		
		boolean isNormal = false;
		while(!pq.isEmpty()) {
			WeightedEdge cur = pq.poll();
			if(visited[cur.getW()])
				continue;
			
			res.add(cur);
			visited[cur.getW()] = true;
			for (Integer weightedEdge : wg.adj(cur.getW())) {
				if(!visited[weightedEdge])
					pq.add(new WeightedEdge(cur.getW(), weightedEdge, wg.weight(cur.getW(), weightedEdge)));
			}
			
			if(res.size() == wg.getV()-1) {
				isNormal = true;
				break;
			}
		}
		
		if(!isNormal)
			res.clear();
		
	}
	
	public ArrayList result() {
		Collections.sort(res); // for testing
		return res;
	}

	public static void main(String[] args) {
		System.out.println(new Prim_try_2020_05_16("wg.txt").result()); 
		System.out.println(new Prim_try_2020_05_16("wg2.txt").result());   //这样下来，使用Prim算法就很方便 不用UF而且pq还是内置的；
		
		System.out.println(new Kruskal_try("wg.txt").result());
		System.out.println(new Kruskal_try("wg2.txt").result());
	}
	
}
